The present invention relates to a decoder, a decoding method, a look-up table, and a decoding program. In particular, the present invention is suitably applied to decode a variable length code.
There is a conventional method of decoding a variable length code in such a manner that a code bit is read bit by bit from an input bit sequence and symbol corresponding to a bit sequence defined in a code table is output as a decoding result when a match occurs between the read bits and the bit sequence. According to this method, decoding can be performed by using a small storage capacity if only code bits corresponding to symbols are held. However, the time required for decoding is long because of one-bit-by-one-bit reading of code bits from the input bit sequence.
On the other hand, there is a method in which, to perform high-speed decoding, symbols from which a decoding result is obtained and the code lengths of the symbols are registered in a look-up table with respect to all entries (candidates) identified by bit sequences corresponding to maximum code lengths.
FIG. 8 is a diagram showing the configuration of such a conventional look-up table.
Referring to FIG. 8(a), a code table 11 is defined in which, for example, a code bit xe2x80x9c1xe2x80x9d is assigned to a symbol S0, code bits xe2x80x9c01xe2x80x9d are assigned to a symbol S1, code bits xe2x80x9c001xe2x80x9d are assigned to a symbol S2, and code bits xe2x80x9c000xe2x80x9d are assigned to a symbol S3.
In this case, since the maximum code length of the code bits is 3, sequence numbers, the symbols and code lengths are registered in a look-up table 12 with respect to 23 entries identified by 3-bit bit sequences, as shown in FIG. 8(b) The sequence numbers may be numbers in decimal notation corresponding to the 3-bit bit sequences.
Bits are read in groups of three bits from the input bit sequence. Each read group of three bits is converted into a decimal number to obtain the sequence number. When the sequence number is obtained, the look-up table 12 is referred to with the sequence number used as a key to obtain the symbol corresponding to the sequence number. The symbol is output as a decoding result while the bit(s) remaining as a result of subtraction of the bits corresponding to the code length of the symbol from bit sequences for 3-bit is returned to the input bit sequence.
For example, if the input bit sequence is xe2x80x9c1010010110 . . . xe2x80x9d, the first three bits xe2x80x9c101xe2x80x9d of this bit sequence is read and this xe2x80x9c101xe2x80x9d is converted into a decimal number to obtain a sequence number xe2x80x9c5xe2x80x9d. The look-up table 12 shown in FIG. 8(b) is referred to with this sequence number xe2x80x9c5xe2x80x9d used as a key to obtain the symbol xe2x80x9cS0xe2x80x9d and the code length xe2x80x9c1xe2x80x9d of the symbol xe2x80x9cS0xe2x80x9d. The symbol xe2x80x9cS0xe2x80x9d is output as a decoding result.
Also, the code length xe2x80x9c1xe2x80x9d of the symbol xe2x80x9cS0xe2x80x9d is compared with the maximum code length xe2x80x9c3xe2x80x9d. Two bits xe2x80x9c01xe2x80x9d corresponding to the difference between the maximum code length xe2x80x9c3xe2x80x9d and the code length xe2x80x9c1xe2x80x9d of the symbol xe2x80x9cS0xe2x80x9d are considered unused in decoding of the symbol xe2x80x9cS0xe2x80x9d and are returned to the input bit sequence xe2x80x9c0010110 . . . xe2x80x9d.
Subsequently, the next three bits xe2x80x9c010xe2x80x9d are read from the input bit sequence xe2x80x9c010010110 . . . xe2x80x9d to which the bits have been returned, and the above-described processing is repeated.
According to the above-described conventional method, decoding can be performed only by reading one time the bit sequence corresponding to the maximum code length from the input bit sequence and, consequently, the speed of decoding can be increased.
The above-described conventional method, however, requires registering symbols and the code lengths of the symbols with respect to all entries identified by bit sequences corresponding to the maximum code length and therefore has the problem that the capacity of look-up table 12 is increased.
That is, in the example shown in FIG. 8, there are only four symbols but it is necessary to register 23 entries of the symbols and the code lengths of the symbols and, therefore, the same symbol is registered in a state of being duplicated a certain number of times.
In particular, if the maximum code length is larger, the number of times one symbol is duplicated when the symbol is registered is increased, resulting in an increase in capacity of the look-up table. For example, if the maximum code length is 16 and if 100 bytes per symbol and one byte for storage of the code length are needed, a capacity of 216xc3x97101 bytes is required.
It is, therefore, an object of the present invention to provide a decoder, a decoding method, a look-up table, and a decoding program enabling decoding at a higher speed with a small storage capacity.
A decoder provided to attain the above-described object according to the present invention is characterized by comprising symbol association means for associating each of reference places for encoded symbols with one of the symbols, and reference place identification means for identifying the reference place for each of symbols when the bit sequence assigned to the symbol and corresponding to the maximum code length is cut out.
It is thereby ensured that while the symbols are not registered in correspondence with all entries identified by the bit sequences corresponding to the maximum code length, each encoded symbol can be identified when the corresponding bit sequence is cut out, and it is possible to reduce the storage capacity while maintaining high-speed decoding performance.
A decoder according to another aspect of the present invention is characterized by comprising reference place information acquisition means for obtaining, on the basis of a bit sequence of a predetermined length, reference place information for a decoding result corresponding to a code contained in the bit sequence, and decoding result acquisition means for obtaining, on the basis of the reference place information obtained by the reference place information acquisition means, the decoding result corresponding to the code contained in the bit sequence.
It is thereby ensured that symbols and entries identified by bit sequences having a predetermined length can be associated with each other while avoiding registration of each symbol to be obtained as a decoding result in a duplicated state, thereby reducing the storage capacity while maintaining high-speed decoding performance.
A decoder according to still another aspect of the present invention, which decodes each of encoded symbols, is characterized by comprising an input buffer which reads from an input bit sequence a bit sequence having a length corresponding to the maximum code length of the symbols, a first sequence table in which reference place information for the symbols is registered with respect to each bit sequence having a length corresponding to the maximum code length of the symbols, a second sequence table in which the symbol and the code length of the symbol are registered with respect to each symbol, first reference means for obtaining the reference place information for the symbol corresponding to a code contained in the bit sequence read to the input buffer by referring to the first sequence table on the basis of the bit sequence, second reference means for obtaining the symbol corresponding to the code contained in the bit sequence and the code length of the symbol by referring to the second sequence table on the basis of the reference place information obtained by the first reference means, and return means for returning to the input bit sequence the remaining bit excluding the bit corresponding to the code length of the symbol from the bit sequence read to the input buffer.
It is thereby ensured that each symbol and the code length of the symbol can be obtained from the second sequence table if only reference places for the symbols are registered in the first sequence table by being associated with the bit sequences having a length corresponding to the maximum code length.
Therefore decoding of the variable length code can be performed by making access two times to the first sequence table and the second sequence table. Also, the need for registering each of the symbols and the code lengths of the symbols in a state of being duplicated a certain number of times by being associated with the bit sequences having a length corresponding to the maximum code length is eliminated, thereby reducing the storage capacity while maintaining high-speed decoding performance.
A decoder according to still another aspect of the present invention, which decodes each of encoded symbols, is characterized by comprising an input buffer which reads from an input bit sequence a bit sequence having a length corresponding to the maximum code length of the symbols, a first sequence table in which reference place information for the symbols is registered with respect to each bit sequence having a length corresponding to the maximum code length of the symbols, a second sequence table in which the symbol and the difference of the code length of the symbol from the maximum code length are registered with respect to each symbol, first reference means for obtaining the reference place information for the symbol corresponding to a code contained in the bit sequence read to the input buffer by referring to the first sequence table on the basis of the bit sequence, second reference means for obtaining the symbol corresponding to the code contained in the bit sequence and the difference by referring to the second sequence table on the basis of the reference place information obtained by the first reference means, and return means for returning to the input bit sequence the bit sequence read to the input buffer by the amount corresponding to the difference.
It is thereby ensured that each symbol and the difference of the code length of the symbol from the maximum code length can be obtained from the second sequence table if only reference places for the symbols are registered in the first sequence table by being associated with the bit sequences having a length corresponding to the maximum code length.
Therefore decoding of the variable length code can be performed by making access two times to the first sequence table and the second sequence table. Also, the number of bits not used in decoding of the variable length code can be obtained directly from the second sequence table, thereby reducing the number of access times, eliminating subtraction processing performed for return of a bit sequence, and further increasing the decoding speed.
According to still another aspect of the present invention, the decoder is characterized in that the first sequence table is divided into a plurality of tables in correspondence with an upper bit sequence and a lower bit sequence having a length corresponding to the maximum code length.
The number of sequences for identification of entries can be reduced thereby to further reduce the storage capacity.
A decoding method according to the present invention is characterized by comprising a step of reading from an input bit sequence a bit sequence having a length corresponding to the maximum code length, a step of obtaining, on the basis of the read bit sequence, reference place information for a symbol corresponding to a code contained in the bit sequence, a step of obtaining, from the obtained reference place information, the symbol corresponding to the code contained in the bit sequence and the code length of the symbol, a step of outputting the obtained symbol as a result of decoding of the code contained in the read bit sequence, and a step of returning to the input bit sequence the bit remaining bit as excluding the bit corresponding to the code length of the symbol from the read bit sequence.
It is thereby ensured that, even for decoding of the variable length code by reading of a length corresponding to the maximum code length, registration of only reference places for symbols associated with bit sequences having a length corresponding to the maximum code length is enough and there is no need to register the same symbol and the code length of the symbol in a state of being duplicated a certain number of times, thus reducing the storage capacity while maintaining high-speed decoding performance.
A look-up table according to the present invention is characterized by comprising a first sequence table in which reference place information for symbols is registered with respect to each of candidates for codes to be decoded, and a second sequence table in which the symbol and the code length of the symbol are registered with respect to each symbol.
It is thereby ensured that access to the symbol corresponding to each of candidates of the codes to be decoded can be made by only referring to the first sequence table one time, and the need for registration of the symbol with respect to each candidate is eliminated, thus improving the decoding speed while limiting the increase in storage capacity.
A look-up table according to another aspect of the present invention is characterized in that symbols and the differences of the code lengths of the symbols from the maximum code length are registered with respect to entries identified by bit sequences having a length corresponding to the maximum code length of the symbols.
It is thereby ensured that each decoded symbol can be output by only making access to the look-up table one time and the number of bits not used in decoding of the symbol can also be obtained thereby. Thus, it is possible to eliminate subtraction processing performed for return of the bit sequence to further increase the decoding speed.
A decoding program according to the present invention, is characterized by executing with a computer a step of reading from an input bit sequence a bit sequence having a length corresponding to the maximum code length, a step of obtaining, on the basis of the read bit sequence, reference place information for a symbol corresponding to a code contained in the bit sequence, a step of obtaining, from the obtained reference place information, the symbol corresponding to the code contained in the bit sequence and the code length of the symbol, a step of outputting the obtained symbol as a result of decoding of the code contained in the read bit sequence, and a step of returning to the input bit sequence the remaining bit excluding the bit corresponding to the code length of the symbol from the read bit sequence.
If this decoding program is installed, the speed of decoding of the variable length code can be increased and the storage capacity of the loop-up table can be reduced.
A decoding program according to another aspect of the present invention is characterized by executing with a computer a step of reading from an input bit sequence a bit sequence having a length corresponding to the maximum code length, a step of obtaining, on the basis of the read bit sequence, reference place information for a symbol corresponding to a code contained in the bit sequence, a step of obtaining, from the obtained reference place information, the symbol corresponding to the code contained in the bit sequence and the difference of the code length of the symbol from the maximum code length, a step of outputting the obtained symbol as a result of decoding of the code contained in the read bit sequence, and a step of returning to the input bit sequence the read bit sequence by the amount corresponding to the difference.
If this decoding program is installed, the number of bits not used in decoding of each symbol can be directly obtained, subtraction processing performed for return of a bit sequence can be eliminated and the decoding speed can be further increased.